package org.codetranslators.common;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Vector;

/**
 * This class implements the depth first search to check if there is at least one path between two 
 * given nodes in a connected graph. The class extends the abstract DepthFirstSearch class to traverse
 * the graph in a depth-first manner.
 * 
 * @author shreesha123
 *
 */
public class ConnectivityTestDFS extends DepthFirstSearch{
	private HashSet<Node> visitedNodes;
	private HashMap edgeVsVisitStatus;
	private Vector backEdges;

	private Node destinationNode;
	
	private boolean pathExists; 
	
	public void setDestinationNode(Node destinationNode){
		this.destinationNode = destinationNode;
	}
	
	public Object execute(DiGraph graph, Node startNode){
		super.execute(graph, startNode);
		pathExists = false;
		
		edgeVsVisitStatus = new HashMap();
		backEdges = new Vector();
		visitedNodes = new HashSet<Node>();
		
		visitedNodes.add(startNode);
		
		int numEdges = graph.getNumEdges();
		for(int i = 0; i < numEdges; i++)
		{
			Boolean visited = new Boolean(false);
			Edge edge = graph.getEdge(i);
			edgeVsVisitStatus.put(edge, visited);
		}
		
		return traverse(startNode);
	}
	
	public boolean isVisited(Edge edge) {
		Boolean visited = (Boolean) edgeVsVisitStatus.get(edge);
		return visited.booleanValue();
	}
	
	public boolean isVisited(Node node){
		return visitedNodes.contains(node);
	}
	
	public void visit(Edge edge){
		edgeVsVisitStatus.put(edge, new Boolean(true));
	}
	
	public void visit(Node node){
		visitedNodes.add(node);		
		if(node == destinationNode)
			pathExists = true;
	}
	
	public boolean isDone(){
		if(pathExists)
			return true;
		return false;
	}
	
	public void traverseDiscovery(Node nextNode, Node node){
	}
	
	public void traverseBack(Edge edge, Node node){
		backEdges.addElement(edge);
	}
	
	public Object getResult(){
		return new Boolean(pathExists);
	}
	
	public Vector getBackEdges(){
		return backEdges;
	}
}
